type name = string
type age = int
type adress = string
type telephone = int
type contact = (name * age * adress * telephone)
type agenda = contact list


let string_of_char c = 
    String.make 1 c ;;


(***** Boite à Outils  *****)

(*** les listes ***)

  (* ajoute x a la liste l, l'ajout n'est pas effectué si x existe deja *)
let rec add_list x = function
    [] -> [x]
  |e::l when x = e -> e::l
  |e::l when x < e -> x::e::l
  |e::l -> e :: add_list x l

let add = add_list 4 [1;2;3;5]
let add = add_list 4 [1;2;3;4;5]


  (* supprime x de la liste l *)
let rec remove_list x l = match l with
[] -> failwith "No Contact Found"
  |e::l when x = e -> l
  |e::l -> e :: remove_list x l

(*let rm = remove_list 4 [1;2;3;5]
let rm = remove_list 4 [1;2;3;4;5]
*)

  (* verifie que x existe dans l *)
let rec exist x = function
    [] -> false
  |e::l when e = x -> true
  |e::l -> exist x l

let ex = exist 4 [1;2;3;5]
let ex = exist 4 [1;2;3;4;5]


(*** l'ordre supérieur ***)

  (* applique f a tout les elements de la liste, puis renvoi la liste *)
let rec map f = function
    [] -> []
  |e::l -> f e::(map f l)

let mp = map (function x -> x + 1) [1;3;5;7;11]


  (* applique a tout les elements de la liste, sans renvoyer la liste *)
let rec iter f l = match l with
[] -> ()
  |e::l -> f e; iter f l

let it = iter (print_int) [1;3;5;7;11]


let rec for_all f = function
[] -> true
|e::l -> f e && for_all f l

let fa = for_all (function x -> x = 0) [0;0;0;0;0]


(*** Les chaines de caracteres ***)

(* convertie en majuscule le caractere c *)
let upper_case c = 
    let c1 = (int_of_char c) in
    if (c1 > 96 && c1 < 123) 
    then char_of_int (c1 - 32) 
    else c

let c = upper_case 'c'
let c = upper_case 'C'

(* convertie en minuscule le caractere c *)
let lower_case c =
    let c1 = (int_of_char c) in
    if (c1 > 64 && c1 < 91) 
    then char_of_int (c1 + 32) 
    else c

let c = lower_case 'C'
let c = lower_case 'c'
(* on leur donne la fonction String.length dans le sujet *)

(* applique la fonction f a tout les caracteres de la chaine str *)
    (* on recupere 1 par 1 les caracteres de s1 en leur appliquant f,
       puis on créé une nouvelle chaine s2 avec les modifications *)

let string_apply f str =
  let rec application f s i l = match i with
    0 -> l 
    | i -> application f s (i-1) ((string_of_char (f(s.[i-1])))^l)
  in application f str (String.length(str)) "";;

let string_uppercase str =
  string_apply upper_case str

let str = string_uppercase "Hello"
let str = string_uppercase "HELLO"


let string_lowercase str =
  string_apply lower_case str

let str = string_lowercase "Hello"
let str = string_lowercase "hello"

(* convertie str en minuscule sauf la premiere lettre qui sera une majuscule *)
let convert_first_maj str =
    let rec application s1 s2 i  = match i with
    i when i = (String.length str) - 1 ->  s2^(string_of_char (lower_case s1.[i]))
    | 0 -> application s1 (s2^(string_of_char (upper_case s1.[i]))) (i + 1)
    | i -> application s1 (s2^(string_of_char (lower_case s1.[i]))) (i + 1)
    in application str "" 0


let l = ["KrisBoul";"JuNioR";"TheneDiel";"YoLo";"2Pac";"LegoLas"] 
let lfirst_maj = map convert_first_maj l

(* creer un contact *)
let create_contact contact =
    let (name, age, adress, tel) = contact in
    let newContact = (convert_first_maj name, age, adress, tel) in
    newContact

let theo = create_contact ("THEO", 20, "87 rue Damremont", 0652302185)
let krisboul = create_contact ("KrisBoul", 42, "EPITA VJ", 0642424242)
let junior = create_contact ("JUnioR", 42, "EPITA VJ", 0641414141)

    (* applique la fonction f au contact de l'agenda *)
let manage_agenda f contact agenda = f contact agenda
 
let add_contact contact agenda = manage_agenda add_list (create_contact contact) agenda

let ag = add_contact theo []
let ag = add_contact krisboul ag
let ag = add_contact junior ag

let remove_contact contact agenda = manage_agenda remove_list contact agenda

(*let ag = remove_contact krisboul ag
*)
  (* modifie contact dans agenda *)
let edit_contact name new_contact agenda = 
    let rec edit x = function
    [] -> failwith "No Contact Found"
    |(e,_,_,_)::l when e = x -> new_contact::l
    |contact::l -> contact :: (edit x l)
    in edit name agenda

let theo = create_contact ("Theo", 20, "EPITA KB", 0652302185)
let ag = edit_contact "Theo" theo ag

  let is_first_maj contact = 
      let (name, _, _, _) = contact in 
      let rec lower s i = match i with
      0 -> int_of_char name.[i] < 97 || int_of_char name.[i] > 122
    | i -> int_of_char name.[i] < 65 || int_of_char name.[i] > 90 && lower s (i - 1)
      in lower name ((String.length name) - 1)

let is_good_format f agenda = for_all f agenda

let test = is_good_format is_first_maj ag
let ag = ("FAIL", 42, "42 rue Du FAIL", 0123456789)::ag
let test = is_good_format is_first_maj ag


let print_contact contact = 
	let (name, age, adress, tel) = contact in
	print_endline 
    ("name : "^name^"  age : "^(string_of_int age)^"  adress : "^adress^
    "  tel : "^(string_of_int tel))

(* affiche le contenue de l agenda *)
let print_agenda agenda = iter print_contact agenda
(*
let print = print_agenda ag
*)
(*** BONUS ***)

(*** Fonctions de tri ***)

    (*** Bubble Sort ***)

let rec bsort s =
    let rec _bsort = function
        | x :: x2 :: xs when x > x2 ->
                x2 :: _bsort (x :: xs)
        | x :: x2 :: xs ->
                x :: _bsort (x2 :: xs)
        | s -> s
    in
    let t = _bsort s in
    if t = s then t
    else bsort t

    (*** Tri par insertion ***)
let tri_insertion comparaison liste =
    let rec insere elem liste = match liste with
    |  [] -> elem::[]
    |  tete::queue ->
            if comparaison elem tete then elem :: liste
            else tete :: insere elem queue
    in

    let rec tri = function
        |  [] -> []
        |  tete::queue -> insere tete
        (tri queue)
    in
    tri liste

    (*** Tri par fusion ***)
    let rec merge = function
        | list, []
        | [], list -> list
        | h1::t1, h2::t2 ->
                if h1 <= h2 then
                    h1 :: merge (t1, h2::t2)
            else
                h2 :: merge
                (h1::t1, t2)

    let rec halve = function
        | []
        | [_] as t1 -> t1, []
        | h::t ->
                let t1, t2 = halve t in
                h::t2, t1

let rec merge_sort = function
    | []
    | [_] as list -> list
    | list -> let l1, l2 = halve list in
    merge (merge_sort l1, merge_sort l2)


 
let agenda = ["Xavière"; "Hugues"; "Aaro"; "Valentin"; "Rebecca"; "Xavier";
    "Dorothée";"Evrard"; "Philippe";"Zéphyrin"; "Véronique";"Nicolas";"Ivan";
    "Aymone";"Ségolène";"Camille";"Bruno";"Patricia";"Mélissa";"Jack";"Fabien";
    "Gwénola";"Olga";"Madeleine";"William";"Oswald";"Teddy";"Babette";"Sabrina";
    "Nastasia";"Zoé";"Cyrille";"Ursula";"Yann";"Ludovic";"Ulrich";"Fulbert";
    "Dahlia";"Rudy";"Gabin";"Edgar";"Peter";"Wolfgang";"Karin";"Théodore";
    "Yvan";"Kurt";"Pascal";"Ladislas";"Justine";"Harold"; "Igor"]

let agenda = merge_sort agenda
